package cn.aylog.algorithm;

import java.util.Arrays;

/**
 * 冒泡排序
 */
public class BubbleSort {
    public static void main(String[] args) {
//        int arr[] = {3, 9, -1, 10, 20};
        int arr1[] = new int[8000];
        int arr2[] = new int[8000];
        for(int i=0; i<8000; i++) {
            int temp = (int)(Math.random()*800000);
            arr1[i] = temp;
            arr2[i] = temp;
        }
        long start = System.currentTimeMillis();
        bubble1(arr1); //  12111 11966
        long end = System.currentTimeMillis();
        System.out.println("bubble1耗时: " + (end - start));

        start = System.currentTimeMillis();
        bubble2(arr2); // 13404 13104
        end = System.currentTimeMillis();
        System.out.println("bubble2耗时: " + (end - start));

//        System.out.println(Arrays.toString(arr));
    }

    /**
     * 常规冒泡(无优化)
     */
    public static void bubble1(int arr[]) {
        int len = arr.length;
        for(int x=0; x<len-1; x++) {
            for(int y=0; y<len-1-x; y++) {
                if(arr[y] > arr[y+1]) {
//                    //常规交换
//                    int temp = arr[y];
//                    arr[y] = arr[y+1];
//                    arr[y+1] = temp;
                    // 无第三方变量
                    arr[y] = arr[y] + arr[y+1];
                    arr[y+1] = arr[y] - arr[y+1];
                    arr[y] = arr[y] - arr[y+1];
                }
            }
        }
    }
    /**
     * 冒泡排序(优化)
     */
    public static void bubble2(int arr[]) { int len = arr.length;
        boolean flag = false;
        for(int x=0; x<len-1; x++) {
            flag = false;
            for(int y=0; y<len-1-x; y++) {
                if(arr[y] > arr[y+1]) {
                    flag = true;
                    // 无第三方变量
                    arr[y] = arr[y] + arr[y+1];
                    arr[y+1] = arr[y] - arr[y+1];
                    arr[y] = arr[y] - arr[y+1];
                }
            }
            if(!flag) {
                break;
            }
        }
    }

}
